Reverse Linked List II

1. Problem Description

Given the head head of a singly linked list and two integers left and right, where left <= right, reverse the nodes from position left to position right and return the reversed list.

2. Approach

3. Implementation

3.1. Three Pointers

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseBetween(head *ListNode, left int, right int) *ListNode {
    // Find the node immediately before left
    dummyHead := &ListNode{Next:head}
    current := dummyHead
    for i := 1; i < left; i++ {
        current = current.Next
    }
    // Save the next node first; this node becomes the node after the tail once [left,right] has been reversed
    next := current.Next
    if next != nil {
        current.Next,next.Next = reverse(next, right-left+1)
    }
    return dummyHead.Next
}

func reverse(head *ListNode, count int) (*ListNode, *ListNode) {
    var prev *ListNode
    current := head
    var next *ListNode
    for i := 0; i < count; i++ {
        next = current.Next
        current.Next = prev
        prev = current
        current = next
    }
    newHead := prev
    newTailNext := current
    return newHead, newTailNext
}

4. References

• 92. Reverse Linked List II - LeetCode